package org.example;

import java.util.*;

public class AppTest04 {
    // 颠倒二进制位
    class Solution {
        // 1
        public int reverseBits(int n) {
            int res = 0;
            for (int i = 0; i < 32; i++) {
                res <<= 1;
                res |= n & 1;
                n >>= 1;
            }
            return res;
        }
        // 2
        public int reverseBits(int n) {
            int res = 0;
            for (int i = 0; i < 32; i++) {
                res <<= 1;
                res |= n & 1;
                n >>= 1;
            }
            return res;
        }
        // 3
        public int reverseBits(int n) {
            int res = 0;
            for (int i = 0; i < 32; i++) {
                res <<= 1;
                res |= n & 1;
                n >>= 1;
            }
            return res;
        }
    }

    // 位1的个数
    class Solution {
        // 1
        public int hammingWeight(int n) {
            int ret = 0;
            for (int i = 0; i < 32; i++) {
                if ((n & (1 << i)) != 0) {
                    ret++;
                }
            }
            return ret;
        }
        // 2
        public int hammingWeight(int n) {
            int ret = 0;
            for (int i = 0; i < 32; i++) {
                if ((n & (1 << i)) != 0) ret++;
            }
            return ret;
        }
        // 3
        public int hammingWeight(int n) {
            int res = 0;
            for (int i = 0; i < 32; i++) {
                if ((n & (1 << i)) != 0) res++;
            }
            return res;
        }
    }

    // 快乐数
    // 1
    class Solution {
        public int getNext(int n) {
            int totalSum = 0;
            while (n > 0) {
                int d = n % 10;
                n /= 10;
                totalSum += d * d;
            }
            return totalSum;
        }

        public boolean isHappy(int n) {
            int slow = n;
            int fast = getNext(n);
            while (fast != 1 && slow != fast) {
                slow = getNext(slow);
                fast = getNext(getNext(fast));
            }
            return fast == 1;
        }
    }
    // 2
    class Solution {
        public int nextSum(int n1) {
            int totalSum = 0;
            while (n1 != 0) {
                int lastDigit = n1 % 10;
                n1 /= 10;
                totalSum += lastDigit * lastDigit;
            }
            return totalSum;
        }

        public boolean isHappy(int n){
            int slow = n;
            int fast = nextSum(n);
            while (fast != 1 && slow != fast){
                slow = nextSum(slow);
                fast = nextSum(nextSum(fast));
            }
            return fast == 1;
        }
    }
    // 3
    class Solution {
        public int next(int n) {
            int sum = 0;
            while (n != 0) {
                int last = n % 10;
                sum += last * last;
                n /= 10;
            }
            return sum;
        }

        public boolean isHappy (int n) {
            int slow = n;
            int fast = next(n);
            while (fast != 1 && fast != slow) {
                slow = next(n);
                fast = next(next(n));
            }
            return fast == 1;
        }
    }

    // 移除链表元素
    class Solution {
        //1
        public ListNode removeElements(ListNode head, int val) {
            ListNode sentinel = new ListNode(0);
            sentinel.next = head;

            ListNode prev = sentinel, curr = head;
            while (curr != null) {
                if (curr.val == val) prev.next = curr.next;
                else prev = curr;
                curr = curr.next;
            }
            return sentinel.next;
        }
        //2
        public ListNode removeElements(ListNode head, int val) {
            ListNode sentinel = new ListNode(0);
            sentinel.next = head;
            ListNode pre = sentinel, curr = head;
            while (curr != null) {
                if (curr.val == val) {
                    pre.next = curr.next;
                // todo 注意逻辑
                } else {
                    pre = pre.next;
                }
                curr = curr.next;
            }
            return sentinel.next;
        }
        //3
        public ListNode removeElements(ListNode head, int val) {
            ListNode sentinel = new ListNode(0);
            sentinel.next = head;
            ListNode pre = sentinel, curr = head;
            while (curr != null) {
                if (curr.val == val) {
                    pre.next = curr.next;
                } else {
                    pre = pre.next;
                }
                curr = curr.next;
            }
            return sentinel.next;
        }
    }

    // 计数质数
    // 1
    class Solution {
        public int countPrimes(int n) {
            int ans = 0;
            for (int i = 2; i < n; ++i) {
                ans += isPrime(i) ? 1 : 0;
            }
            return ans;
        }

        public boolean isPrime(int x) {
            for (int i = 2; i * i <= x ; i++) {
                if (x % i == 0) return false;
            }
            return true;
        }
    }
    // 2
    class Solution {
        public int countPrimes (int n) {
            int res = 0;
            for (int i = 2; i < n; i++) {
                res += isPrime(i) ? 1 : 0;
            }
            return res;
        }

        public boolean isPrime(int x) {
            // todo 注意<=
            for (int i = 2; i * i <= x ; i++) {
                if (x % i == 0) return false;
            }
            return true;
        }
    }
    // 3
    class Solution {
        public int countPrimes (int n) {
            int res = 0;
            for (int i = 2; i < n ; i++) {
                res += isPrime(i) ? 1 : 0;
            }
            return res;
        }

        public boolean isPrime(int x) {
            for (int i = 2; i * i <= x ; i++) {
                if (x % i == 0) return false;
            }
            return true;
        }
    }

    // 同构字符串
    class Solution {
        // 1
        public boolean isIsomorphic(String s, String t) {
            Map<Character, Character> s2t = new HashMap<>();
            Map<Character, Character> t2s = new HashMap<>();
            int len = s.length();
            for (int i = 0; i < len; i++) {
                char x = s.charAt(i), y = t.charAt(i);
                if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
                    return false;
                }
                s2t.put(x, y);
                t2s.put(y, x);
            }
            return true;
        }

        // 2
        public boolean isIsomorphic(String s, String t) {
            Map<Character, Character> s2t = new HashMap<>();
            Map<Character, Character> t2s = new HashMap<>();
            int len = s.length();
            for (int i = 0; i < len; i++) {
                char sChar = s.charAt(i), tChar = t.charAt(i);
                if ((s2t.containsKey(sChar) && tChar != s2t.get(sChar)) ||
                        (t2s.containsKey(tChar) && sChar != t2s.get(tChar))) return false;

                s2t.put(sChar, tChar);
                t2s.put(tChar, sChar);
            }
            return true;
        }

        // 3
        public boolean isIsomorphic(String s, String t) {
            Map<Character, Character> s2t = new HashMap<>();
            Map<Character, Character> t2s = new HashMap<>();
            int len = s.length();
            for (int i = 0; i < len; i++) {
                Character sChar = s.charAt(i);
                Character tChar = t.charAt(i);
                if ((s2t.containsKey(sChar) && s2t.get(sChar) != tChar) ||
                        (t2s.containsKey(tChar) && t2s.get(tChar) != sChar)) return false;
                s2t.put(sChar, tChar);
                t2s.put(tChar, sChar);
            }
            return true;
        }
    }

    // 反转链表
    class Solution {
        // 1
        public ListNode reverseList(ListNode head) {
            ListNode pre = null, curr = head;
            while (curr != null) {
                ListNode next = curr.next;
                curr.next = pre;
                pre = curr;
                curr = next;
            }
            return pre;
        }
        // 2
        public ListNode reverseList(ListNode head) {
            ListNode pre = null, curr = head;
            while (curr != null) {
                ListNode next = curr.next;
                curr.next = pre;
                pre = curr;
                curr = next;
            }
            return pre;
        }
        // 3
        public ListNode reverseList(ListNode head) {
            ListNode pre = null, curr = head;
            while (curr != null) {
                ListNode next = curr.next;
                curr.next = pre;
                pre = curr;
                curr = next;
            }
            return pre;
        }
    }

    // 存在重复元素
    class Solution {
        // 1
        public boolean containsDuplicate(int[] nums) {
            Set<Integer> set1 = new HashSet<>();
            for (int x : nums) {
                if (!set1.add(x)) return true;
            }
            return false;
        }
        // 2
        public boolean containsDuplicate(int[] nums) {
            Set<Integer> set1 = new HashSet<>();
            for (int num : nums) {
                if (!set1.add(num)) return true;
            }
            return false;
        }
        // 3
        public boolean containsDuplicate(int[] nums) {
            Set<Integer> set1 = new HashSet<>();
            for (int num : nums) {
                if(!set1.add(num)) return true;
            }
            return false;
        }
    }

    // 存在重复元素2
    class Solution {
        // 1
        public boolean containsNearbyDuplicate(int[] nums, int k) {
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < nums.length; i++) {
                if (set.contains(nums[i])) return true;
                set.add(nums[i]);
                if (set.size() > k) set.remove(nums[i-k]);
            }
            return false;
        }
        // 2
        public boolean containsNearbyDuplicate(int[] nums, int k) {
            Set<Integer> set1 = new HashSet<>();
            for (int i = 0; i < nums.length; i++) {
                if (set1.contains(nums[i])) return true;
                set1.add(nums[i]);
                if (set1.size() > k) {
                    set1.remove(nums[i - k]);
                }
            }
            return false;
        }
        // 3
        public boolean containsNearbyDuplicate(int[] nums, int k) {
            Set<Integer> set1 = new HashSet<>();
            for (int i = 0; i < nums.length; i++) {
                if (set1.contains(nums[i])) return true;
                set1.add(nums[i]);
                if (set1.size() > k) {
                    set1.remove(nums[i-k]);
                }
            }
            return false;
        }
    }

    // 用队列实现栈
    // 1
    class MyStack {
        Queue<Integer> queue1;
        Queue<Integer> queue2;
        /** Initialize your data structure here. */
        public MyStack() {
            queue1 = new LinkedList<>();
            queue2 = new LinkedList<>();
        }

        /** Push element x onto stack. */
        public void push(int x) {
            queue2.offer(x);
            while (!queue1.isEmpty()) {
                queue2.offer(queue1.poll());
            }
            Queue<Integer> tmp = queue1;
            queue1 = queue2;
            queue2 = tmp;
        }

        /** Removes the element on top of the stack and returns that element. */
        public int pop() {
            return queue1.poll();
        }

        /** Get the top element. */
        public int top() {
            return queue1.peek();
        }

        /** Returns whether the stack is empty. */
        public boolean empty() {
            return queue1.isEmpty();
        }
    }
    // 3
    class MyStack {
        Queue<Integer> queue1 = new LinkedList<>();
        Queue<Integer> queue2 = new LinkedList<>();
        /** Initialize your data structure here. */
        public MyStack() {}
        /** Push element x onto stack. */
        public void push(int x) {
            queue2.offer(x);
            while (!queue1.isEmpty()) {
                queue2.offer(queue1.poll());
            }
            Queue<Integer> tmp = queue1;
            queue1 = queue2;
            queue2 = tmp;
        }

        /** Removes the element on top of the stack and returns that element. */
        public int pop() {
            return queue1.poll();
        }

        /** Get the top element. */
        public int top() {
            return queue1.peek();
        }

        /** Returns whether the stack is empty. */
        public boolean empty() {
            return queue1.isEmpty();
        }
    }

    // 翻转二叉树
    class Solution {
        // 1
        public TreeNode invertTree(TreeNode root) {
            if (root == null) return null;
            TreeNode left = invertTree(root.left);
            TreeNode right = invertTree(root.right);
            root.left = right;
            root.right = left;
            return root;
        }
        // 2
        public TreeNode invertTree(TreeNode root) {
            if (root == null) return null;
            TreeNode left = invertTree(root.left);
            TreeNode right = invertTree(root.right);
            root.left = right;
            root.right = left;
            return root;
        }
        // 3
        public TreeNode invertTree(TreeNode root) {
            if (root == null) return null;
            TreeNode left = invertTree(root.left);
            TreeNode right = invertTree(root.right);
            root.left = right;
            root.right = left;
            return root;
        }
    }

    // 汇总区间
    class Solution {
        // 1
        public List<String> summaryRanges(int[] nums) {
            List<String> ret = new ArrayList<>();
            int i = 0;
            while (i < nums.length) {
                int low = i;
                i++;
                while (i < nums.length && nums[i] == nums[i - 1] + 1) {
                    i++;
                }
                int high = i - 1;
                StringBuffer sb = new StringBuffer(Integer.toString(nums[low]));
                if (low < high){
                    sb.append("->");
                    sb.append(Integer.toString(nums[high]));
                }
                ret.add(sb.toString());
            }
            return ret;
        }
        // 2
        public List<String> summaryRanges(int[] nums) {
            List<String> res = new ArrayList<>();
            // todo 用while循环
            int i = 0;
            while (i < nums.length) {
                int low = i;
                i++;
                // todo 用while循环，注意i边界
                while (i < nums.length && nums[i] == nums[i - 1] + 1) i++;
                int high = i - 1;
                // todo 构造函数需要String类型参数
                StringBuffer sb = new StringBuffer(Integer.toString(nums[low]));
                if (low < high) {
                    sb.append("->");
                    sb.append(nums[high]);
                }
                res.add(sb.toString());
            }
            return res;
        }
        // 3
        public List<String> summaryRanges(int[] nums) {
            List<String> res= new ArrayList<>();
            int i = 0;
            while (i < nums.length) {
                int low = i;
                i++;
                while (i < nums.length && nums[i] == nums[i - 1] + 1) i ++;
                int high = i - 1;

                StringBuffer sb = new StringBuffer(Integer.toString(nums[low]));
                if (low < high) {
                    sb.append("->");
                    sb.append(nums[high]);
                }
                res.add(sb.toString());
            }
            return res;
        }
    }

    // 2的幂
    class Solution {
        // 1
        public boolean isPowerOfTwo(int n) {
            if (n == 0) return false;
            while (n % 2 == 0) n /= 2;
            return n == 1;
        }
        // 2
        public boolean isPowerOfTwo(int n) {
            if (n == 0) return false;
            while (n % 2 == 0) n /= 2;
            return n == 1;
        }
    }

    // 2的幂
    class Solution {
        // 1
        public boolean isPowerOfTwo(int n) {
            if (n == 0) return false;
            while (n % 2 == 0) n /= 2;
            return n == 1;
        }
        // 2
        public boolean isPowerOfTwo(int n) {
            if (n == 0) return false;
            while (n % 2 == 0) n /= 2;
            return n == 1;
        }
        // 3
        public boolean isPowerOfTwo(int n) {
            if (n == 0) return false;
            while (n % 2 == 0) n /= 2;
            return n == 1;
        }
    }

    // 用栈实现队列 1
    class MyQueue {
        Deque<Integer> inStack;
        Deque<Integer> outStack;
        public MyQueue() {
            inStack = new LinkedList<>();
            outStack = new LinkedList<>();
        }

        public void push(int x) {
            inStack.add(x);
        }

        public int pop() {
            if (outStack.isEmpty()) in2out();
            return outStack.pop();
        }

        public int peek() {
            if (outStack.isEmpty()) in2out();
            return outStack.peek();
        }
        public boolean empty() {
            return inStack.isEmpty() && outStack.isEmpty();
        }

        private void in2out() {
            while (!inStack.isEmpty()) outStack.add(inStack.pop());
        }
    }
    // 用栈实现队列 2
    // 完成
    // 用栈实现队列 3
    class MyQueue {

        Deque<Integer> inStack;
        Deque<Integer> outStack;

        public MyQueue() {
            inStack = new LinkedList<>();
            outStack = new LinkedList<>();
        }

        public void push(int x) {
            inStack.push(x);
        }

        public int pop() {
            if (outStack.isEmpty()) {
                in2out();
            }
            return outStack.pop();
        }

        public int peek() {
            if (outStack.isEmpty()) {
                in2out();
            }
            return outStack.peek();
        }
        public boolean empty() {
            return inStack.isEmpty() && outStack.isEmpty();
        }

        private void in2out() {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }

    // 回文链表
    class Solution {
        // 1
        public boolean isPalindrome(ListNode head) {
            List<Integer> vals = new ArrayList<>();

            ListNode curr = head;
            while (curr != null) {
                vals.add(curr.val);
                curr = curr.next;
            }

            int front = 0, back = vals.size() - 1;
            while (front < back) {
                if (!vals.get(front).equals(vals.get(back))) return false;
                front++;
                back--;
            }
            return true;
        }
        // 2
        public boolean isPalindrome(ListNode head) {

            List<Integer> tmp = new ArrayList<>();
            ListNode curr = head;
            while (curr != null) {
                tmp.add(curr.val);
                curr = curr.next;
            }

            int front = 0, back = tmp.size() - 1;
            while (front < back) {
                if (tmp.get(front) != tmp.get(back)) return false;
                front++;
                back--;
                }
            return true;
            }
        // 3
        public boolean isPalindrome(ListNode head) {
            List<Integer> tmp = new ArrayList<>();
            ListNode curr = head;
            while (curr != null) {
                tmp.add(curr.val);
                curr = curr.next;
            }

            int front = 0, back = tmp.size() - 1;
            while (front < back) {
                if (tmp.get(front) != tmp.get(back)) return false;
                front++;
                back--;
            }
            return true;
        }
    }

    // 二叉搜索树的最近公共祖先
    class Solution {
        // 1
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            TreeNode ancestor = root;
            while (true) {
                if (p.val < ancestor.val && q.val < ancestor.val) ancestor = ancestor.left;
                // todo 注意加else
                else if (p.val > ancestor.val && q.val > ancestor.val) ancestor = ancestor.right;
                else break;
            }
            return ancestor;
        }
        // 2
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            TreeNode ancestor = root;
            while (true) {
                if (p.val < ancestor.val && q.val < ancestor.val) ancestor = ancestor.left;
                else if (p.val > ancestor.val && q.val > ancestor.val) ancestor = ancestor.right;
//                else break;
                else return ancestor;
            }
//            return ancestor;
        }
        // 3
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            TreeNode ancestor = root;
            while (true) {
                if (p.val < ancestor.val && q.val < ancestor.val) ancestor = ancestor.left;
                else if (p.val > ancestor.val && q.val > ancestor.val) ancestor = ancestor.right;
                else return ancestor;
            }
        }
    }

    // 删除链表中的节点
    class Solution {
        // 1
        public void deleteNode(ListNode node) {
            node.val = node.next.val;
            node.next = node.next.next;
        }
        // 2 ok
        // 3
        public void deleteNode(ListNode node) {
            node.val = node.next.val;
            node.next = node.next.next;
        }
    }

    // 有效的字母异位词
    class Solution {
        // 1
        public boolean isAnagram(String s, String t) {
            if (s.length() != t.length()) return false;
            Map<Character, Integer> table = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                table.put(ch, table.getOrDefault(ch, 0) + 1);
            }
            for (int i = 0; i < t.length(); i++) {
                char ch = t.charAt(i);
                table.put(ch, table.getOrDefault(ch, 0) - 1);
                if (table.get(ch) < 0) return false;
            }
            return true;
        }
        // 2
        public boolean isAnagram(String s, String t) {
            if (s.length() != t.length()) return false;
            Map<Character, Integer> table = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                table.put(s.charAt(i), table.getOrDefault(s.charAt(i), 0) + 1);
            }
            for (int i = 0; i < t.length(); i++) {
                table.put(t.charAt(i), table.getOrDefault(t.charAt(i), 0) - 1);
                if (table.get(t.charAt(i)) < 0) return false;
            }
            return true;
        }
        // 3
        public boolean isAnagram(String s, String t) {
            if (s.length() != t.length()) return false;
            Map<Character, Integer> tmp = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                tmp.put(s.charAt(i), tmp.getOrDefault(s.charAt(i), 0) + 1);
            }
            for (int i = 0; i < t.length(); i++) {
                tmp.put(t.charAt(i), tmp.getOrDefault(t.charAt(i), 0) - 1);
                if (tmp.get(t.charAt(i)) < 0) return false;
            }
            return true;
        }
    }

    // 二叉树的所有路径
    class Solution {
        // 1
        public List<String> binaryTreePaths(TreeNode root) {
            List<String> paths = new ArrayList<>();
            if (root == null) return paths;

            Queue<TreeNode> nodeQueue = new LinkedList<>();
            Queue<String> pathQueue = new LinkedList<>();
            nodeQueue.offer(root);
            pathQueue.offer(Integer.toString(root.val));

            while (!nodeQueue.isEmpty()) {
                TreeNode node = nodeQueue.poll();
                String path = pathQueue.poll();
                if (node.left == null && node.right == null) paths.add(path);
                else{
                    if (node.left != null) {
                        nodeQueue.offer(node.left);
                        pathQueue.offer(new StringBuffer(path).append("->").append(node.left.val).toString());
                    }
                    if (node.right != null) {
                        nodeQueue.offer(node.right);
                        pathQueue.offer(new StringBuffer(path).append("->").append(node.right.val).toString());
                    }
                }
            }
            return paths;
        }
        // 2
        public List<String> binaryTreePaths(TreeNode root) {
            List<String> paths = new ArrayList<>();
            if (root == null) return paths;

            Queue<TreeNode> nodeQueue = new LinkedList<>();
            Queue<String> pathQueue = new LinkedList<>();
            nodeQueue.offer(root);
            pathQueue.offer(Integer.toString(root.val));

            while (!pathQueue.isEmpty()) {
                TreeNode node = nodeQueue.poll();
                String path = pathQueue.poll();
                if (node.left == null && node.right == null) {
                    paths.add(path);
                } else {
                    if (node.left != null) {
                        nodeQueue.offer(node.left);
                        pathQueue.offer(path + "->" +Integer.toString(node.left.val));
                    }
                    if (node.right != null) {
                        nodeQueue.offer(node.right);
                        pathQueue.offer(path + "->" +Integer.toString(node.right.val));
                    }
                }
            }
            return paths;
        }
        // 3
        public List<String> binaryTreePaths(TreeNode root) {
            List<String> paths = new ArrayList<>();
            if (root == null) return paths;
            Queue<TreeNode> nodeQueue= new LinkedList<>();
            Queue<String> pathQueue = new LinkedList<>();
            nodeQueue.offer(root);
            pathQueue.offer(Integer.toString(root.val));

            while (!pathQueue.isEmpty()) {
                TreeNode node = nodeQueue.poll();
                String path = pathQueue.poll();
                if (node.left == null && node.right == null) {
                    paths.add(path);
                } else {
                    if (node.left != null) {
                        nodeQueue.offer(node.left);
                        pathQueue.offer(path + "->" + node.left.val);
                    }
                    if (node.right != null) {
                        nodeQueue.offer(node.right);
                        pathQueue.offer(path + "->" + node.right.val);
                    }
                }
            }
            return paths;
        }
    }

    // 丑数
    class Solution {
        // 1
        public boolean isUgly(int n) {
            if (n <= 0) return false;
            int[] factors = {2, 3, 5};
            for (int factor : factors) {
                while (n % factor == 0) n /= factor;
            }
            return n == 1;
        }
        // 2
        public boolean isUgly(int n) {
            if (n == 0) return false;
            int[] factors = new int[]{2, 3, 5};
            for (int factor : factors) {
                while (n % factor == 0) {
                    n /= factor;
                }
            }
            return n == 1;
        }
        // 3
        public boolean isUgly(int n) {
            if (n == 0) return false;
            int[] factors = new int[] {2, 3, 5};
            for (int factor : factors) {
                while (n % factor == 0) {
                    n /= factor;
                }
            }
            return n == 1;
        }
    }

    // 缺失数字
    class Solution {
        // 1
        public int missingNumber(int[] nums) {
            int missing = nums.length;
            for (int i = 0; i < nums.length; i++) {
                missing ^= i ^ nums[i];
            }
            return missing;
        }

        // 2
        public int missingNumber(int[] nums) {
            int missing = nums.length;
            for (int i = 0; i < nums.length; i++) {
                missing ^= i ^ nums[i];
            }
            return missing;
        }

        // 3
        public int missingNumber(int[] nums) {
            int missing = nums.length;
            for (int i = 0; i < nums.length; i++) {
                missing ^= nums[i] ^ i;
            }
            return missing;
        }
    }

    // first bad version
    class Solution {
        // 1
        public int firstBadVersion(int n) {
            int left = 1, right = n;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (isBadVersion(mid)) right = mid;
                else left = mid + 1;
            }
            return left;
        }
        // 2
        public int firstBadVersion(int n) {
            int left = 1, right = n;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (isBadVersion(mid)) {
                    right = mid;
                }
                else {
                    left = mid + 1;
                }
            }
            return left;
        }
        // 3
        public int firstBadVersion(int n) {
            int left = 1, right = n;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (isBadVersion(mid)) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
    }

    // move zeros 1
    class Solution {
        public void moveZeroes(int[] nums) {
            int n = nums.length, left = 0, right = 0;
            while (right < n) {
                if (nums[right] != 0) {
                    swap(nums, left, right);
                    left++;
                }
                right++;
            }
        }
        public void swap(int[] nums, int left, int right){
            int tmp = nums[right];
            nums[right] = nums[left];
            nums[left] = tmp;
        }
    }
    // move zeros 2
    class Solution {
        public void moveZeroes(int[] nums) {
            int left = 0, right = 0;
            while (right < nums.length) {
                if (nums[right] != 0) {
                    swap(nums, left, right);
                    left++;
                }
                right++;
            }
        }
        public void swap(int[] nums, int left, int right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
    }
    // move zeros 3
    class Solution {
        public void moveZeroes(int[] nums) {
            int left = 0, right = 0;
            while (right < nums.length) {
                if (nums[right] != 0) {
                    swap(nums, left, right);
                    left++;
                }
                right++;
            }
        }

        public void swap(int[] nums, int left, int right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
    }

    // word pattern
    // 1
    class Solution {
        public boolean wordPattern(String pattern, String s) {
            HashMap<Character, String> mapChar = new HashMap<>();
            HashMap<String, Character> mapWord = new HashMap<>();
            String[] words = s.split(" ");

            if (words.length != pattern.length()) return false;
            for (int i = 0; i < words.length; i++) {
                char c = pattern.charAt(i);
                String w = words[i];
                if (!mapChar.containsKey(c)) {
                    if (mapWord.containsKey(w)) {
                        return false;
                    } else {
                        mapChar.put(c, w);
                        mapWord.put(w, c);
                    }
                } else {
                    if (!mapChar.get(c).equals(w)) return false;
                }
            }
            return true;
        }
    }
    // 2
    class Solution {
        public boolean wordPattern(String pattern, String s) {
            HashMap<Character, String> charMap = new HashMap<>();
            HashMap<String, Character> wordMap = new HashMap<>();
            String[] words = s.split(" ");
            if (words.length != pattern.length()) return false;
            for (int i = 0; i < pattern.length(); i++) {
                Character c = pattern.charAt(i);
                String w = words[i];
                if (!charMap.containsKey(c)) {
                    if (wordMap.containsKey(w)) {
                        return false;
                    } else {
                        charMap.put(c, w);
                        wordMap.put(w, c);
                    }
                } else {
                    if (!charMap.get(c).equals(w)) return false;
                }
            }
            return true;
        }
    }
    // 3
    class Solution {
        public boolean wordPattern(String pattern, String s) {
            HashMap<Character, String> charMap = new HashMap<>();
            HashMap<String, Character> wordMap = new HashMap<>();
            String[] words = s.split(" ");
            if (pattern.length() != words.length) return false;
            for (int i = 0; i < pattern.length(); i++) {
                Character c = pattern.charAt(i);
                String w = words[i];
                if (!charMap.containsKey(c)) {
                    if (wordMap.containsKey(w)) {
                        return false;
                    } else {
                        charMap.put(c, w);
                        wordMap.put(w, c);
                    }
                } else {
                    if (!charMap.get(c).equals(w)) return false;
                }
            }
            return true;
        }
    }

    // nim game 1 2
    class Solution {
        public boolean canWinNim(int n) {
            return n % 4 != 0;
        }
    }

    // Range Sum Query 1
    class NumArray {
        private int[] sum;
        public NumArray(int[] nums) {
            sum = new int[nums.length + 1];
            for (int i = 0; i < nums.length; i++) {
                sum [i + 1] = sum[i] + nums[i];
            }
        }

        public int sumRange(int left, int right) {
            return sum[right + 1] - sum[left];
        }
    }
}
